package com.yoshino.leetcode.improve40.twentysecond;

class Solution {
    // 后缀树，
    class SuffixNode {
        // 长度
        Integer len;
        SuffixNode[] next;
        public SuffixNode() {
            next = new SuffixNode[26];
            len = 0;
        }
    }

    SuffixNode root = new SuffixNode();
    public int minimumLengthEncoding(String[] words) {
        int res = 0;
        for (String word : words) {
            // 是否找到后缀
            SuffixNode cur = root;
            boolean isNew = false;
            for (int i = word.length() - 1; i >= 0; i--) {
                int ind = word.charAt(i) - 'a';
                if (cur.next[ind] == null) {
                    cur.next[ind] = new SuffixNode();
                    isNew = true;
                }
                cur = cur.next[ind];
                // 出现 me , time 的情况应该去掉前一个
                if (cur.len > 0 && cur.len < word.length()) {
                    // 该后缀可以被替换
                    res -= (cur.len + 1);
                    cur.len = 0;
                }
            }
            if (isNew) {
                cur.len = word.length();
                res += word.length() + 1;
            }
        }
        return res;
    }


    // 前缀树 : 异或 当 当前值为0 则找 结点值为 1 的（因为从大往下找，所以不用回溯
    // 后缀树：找到当前数的结尾时，需要遍历剩余的后续子树，因为不确定哪个1最深

    class PrefixNode{
        // 左节点表示 0
        PrefixNode left;
        PrefixNode right;
    }
    PrefixNode root2 = new PrefixNode();
    // 最高位 31
    int K = 30;
    public int findMaximumXOR(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 1; i < n; i++) {
            // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
            add(nums[i - 1]);
            // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
            res = Math.max(res, check(nums[i]));
        }
        return res;
    }

    private int check(int num) {
        PrefixNode cur = root2;
        int res = 0;
        for (int i = K; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (bit == 0) {
                // 往 1 的方向走
                if (cur.right != null) {
                    cur = cur.right;
                    res = res * 2 + 1;
                } else {
                    cur = cur.left;
                    res = res * 2;
                }
            } else {
                if (cur.left != null) {
                    cur = cur.left;
                    res = res * 2 + 1;
                } else {
                    cur = cur.right;
                    res = res * 2;
                }
            }
        }
        return res;
    }

    private void add(int num) {
        PrefixNode cur = root2;
        for (int i = K; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (bit == 0) {
                if (cur.left == null) {
                    cur.left = new PrefixNode();
                }
                cur = cur.left;
            } else {
                if (cur.right == null) {
                    cur.right = new PrefixNode();
                }
                cur = cur.right;
            }
        }
    }
}